/*
 * IBM Corporation.
 * Copyright (c) 2014 All Rights Reserved.
 */

package com.ibm.iisp.common.util;

/**
 * 类作用：
 * 
 * @author JohnnyZhou@cn.ibm.com 使用说明：
 */
public class Dijkstra {
	static Integer noPath = null;
	static int MaxSize = 1000;

	public static void main(String[] s) {
		/*Integer[][] g = {
			{ noPath, noPath, 10, noPath, 30, 100 },
			{ noPath, noPath, 5, noPath, noPath, noPath },
			{ noPath, noPath, noPath, 50, noPath, noPath },
			{ noPath, noPath, noPath, noPath, noPath, 10 },
			{ noPath, noPath, noPath, 20, noPath, 60 },
			{ noPath, noPath, noPath, noPath, noPath, noPath }
		};*/
		Integer[][] g = {
			{ noPath, 7, 9, noPath, noPath, 14 },
			{ 7, noPath, 10, 15, noPath, noPath},
			{ 9, 10, noPath, 11, noPath, 2 },
			{ noPath, 15, 11, noPath, noPath, 2 },
			{ noPath, noPath, noPath, 6, noPath, 9 },
			{ 14, noPath, 2, noPath, 9, noPath }
		};
		int[][] path1 = new int[g.length][g.length];
		// for (int i = 0; i < path1.length; i++) {
		// path1[i] = new int[g.length];
		// }
		Integer[] dist1 = getShortedPathAll(g, 0, path1);
		for (int i = 0; i < path1.length; i++) {
			for (int j = 0; j < path1.length; j++) {
				System.out.print(path1[i][j] + " ");
			}
			System.out.println();
		}
		for (int i = 0; i < dist1.length; i++)
			System.out.println("Length:" + dist1[i]);

	}

	// 从某一源点出发，找到到某一结点的最短路径
	public static int getShortedPath(Integer[][] g, int start, int end, int[] path) {
		int length = g.length;
		boolean[] s = new boolean[length]; // 表示找到起始结点与当前结点间的最短路径
		int min; // 最小距离临时变量
		int curNode = 0; // 临时结点，记录当前正计算结点
		Integer[] dist = new Integer[length];
		int[] prev = new int[length];

		// 初始结点信息
		for (int v = 0; v < length; v++) {
			s[v] = false;
			dist[v] = g[start][v];
			if (dist[v] == null || dist[v] > MaxSize) {
				prev[v] = 0;
			} else {
				prev[v] = start;
			}
		}
		path[0] = end;
		dist[start] = 0;
		s[start] = true;
		// 主循环
		for (int i = 1; i < length; i++) {
			min = MaxSize;
			for (int w = 0; w < length; w++) {
				if (!s[w] && dist[w] != null && dist[w] < min) {
					curNode = w;
					min = dist[w];
				}
			}

			s[curNode] = true;

			for (int j = 0; j < length; j++) {
				Integer wt = g[curNode][j];
				if (wt == null) {
					wt = 2000;
				}
				Integer wt2 = dist[j];
				if (wt2 == null) {
					wt2 = 2000;
				}

				if (!s[j] && min + wt < wt2) {
					dist[j] = min + wt;
					prev[j] = curNode;
				}
			}

		}
		// 输出路径结点
		int e = end, step = 0;
		while (e != start) {
			step++;
			path[step] = prev[e];
			e = prev[e];
		}
		for (int i = step; i > step / 2; i--) {
			int temp = path[step - i];
			path[step - i] = path[i];
			path[i] = temp;
		}
		return dist[end];
	}

	// 从某一源点出发，找到到所有结点的最短路径
	public static Integer[] getShortedPathAll(Integer[][] graph, int start, int[][] path) {
		int length = graph.length;
		// int[] PathID = new int[length];// 路径（用编号表示）
		boolean[] s = new boolean[length]; // 表示找到起始结点与当前结点间的最短路径
		int min; // 最小距离临时变量
		int curNode = 0; // 临时结点，记录当前正计算结点
		Integer[] dist = new Integer[length];
		int[] prev = new int[length];
		// 初始结点信息

		for (int v = 0; v < length; v++) {
			s[v] = false;
			dist[v] = graph[start][v];
			if (dist[v] == null || dist[v] > MaxSize) {
				prev[v] = 0;
			} else {
				prev[v] = start;
			}
			path[v][0] = v;
		}

		dist[start] = 0;
		s[start] = true;
		// 主循环
		for (int i = 1; i < length; i++) {
			min = MaxSize;
			for (int w = 0; w < length; w++) {
				if (!s[w] && dist[w] != null && dist[w] < min) {
					curNode = w;
					min = dist[w];
				}
			}

			s[curNode] = true;

			for (int j = 0; j < length; j++) {
				Integer wt = graph[curNode][j];
				if (wt == null) {
					wt = 2000;
				}
				Integer wt2 = dist[j];
				if (wt2 == null) {
					wt2 = 2000;
				}
				if (!s[j] && min + wt < wt2) {
					dist[j] = min + graph[curNode][j];
					prev[j] = curNode;
				}
			}
		}
		// 输出路径结点
		for (int k = 0; k < length; k++) {
			int e = k, step = 0;
			while (e != start) {
				step++;
				path[k][step] = prev[e];
				e = prev[e];
			}
			for (int i = step; i > step / 2; i--) {
				int temp = path[k][step - i];
				path[k][step - i] = path[k][i];
				path[k][i] = temp;
			}
		}
		return dist;

	}

}
